#define _CRT_SECURE_NO_WARNINGS

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
    *returnSize = temperaturesSize;
    int* ret = (int*)malloc(sizeof(int) * temperaturesSize);
    memset(ret, 0, sizeof(int) * temperaturesSize);

    int* stack = (int*)malloc(sizeof(int) * temperaturesSize);
    int top = 0;

    for (int i = 0; i < temperaturesSize; i++)
    {
        if (top == 0 || temperatures[i] <= temperatures[stack[top - 1]])
        {
            stack[top++] = i;
        }
        else
        {
            while (top != 0 && temperatures[i] > temperatures[stack[top - 1]])
            {
                ret[stack[top - 1]] = i - stack[top - 1];
                top--;
            }

            stack[top++] = i;
        }
    }

    free(stack);
    return ret;
}